#include <cnix/errno.h>
#include <cnix/string.h>
#include <cnix/stat.h>
#include "ext2.h"

extern void ext2_init_block_alloc_info(struct inode *inode);
extern unsigned long ext2_new_blocks(struct inode *inode,ext2_fsblk_t goal,unsigned long *count);
static void ext2_inode_free(struct inode *);
static BOOLEAN ext2_inode_can_delete(struct inode *);
static int ext2_inode_truncate(struct inode *, loff_t);
static loff_t ext2_inode_size(struct inode *);
static void ext2_inode_setsize(struct inode *, loff_t);
static mode_t ext2_inode_mode(struct inode *);
static void ext2_inode_setmode(struct inode *, mode_t);
static dev_t ext2_inode_realdev(struct inode *);
static BOOLEAN ext2_inode_real_filename(char * page, struct inode *, int * error);
static BOOLEAN ext2_inode_minode(struct inode *, off_t, unsigned long);
static BOOLEAN ext2_inode_noitem(struct inode *);
static BOOLEAN ext2_inode_additem(struct inode *, const char *, int *, struct inode*);
static BOOLEAN ext2_inode_delitem(struct inode *, const char *, int *);
static ino_t ext2_inode_findson(struct inode *, const char *);
static uid_t ext2_inode_getuid(struct inode * inoptr);
static void ext2_inode_setuid(struct inode *, uid_t);
static gid_t ext2_inode_getgid(struct inode *);
static void ext2_inode_setgid(struct inode *, gid_t);
static void ext2_inode_mknod(struct inode *, dev_t);
static unsigned long ext2_inode_bmap(struct inode *, loff_t);
static int ext2_inode_blocksize(struct inode *);
static loff_t ext2_inode_max_filesize(struct inode *);
static void ext2_inode_update(struct inode *, time_t, time_t, time_t);
static nlink_t ext2_inode_change_nlinks(struct inode *, int);
static int ext2_inode_get_name_of_son(struct inode *, ino_t, char *, int);
static int ext2_inode_stat(struct inode *, struct stat *);
static int ext2_inode_readdir(int, struct dirent *);
static int ext2_inode_readlink(struct inode*,char *buf,size_t buf_size);

struct inode_operation ext2_inode_operation = {
	.free = ext2_inode_free,
	.can_delete = ext2_inode_can_delete,
	.truncate =  ext2_inode_truncate,
	.size = ext2_inode_size,
	.setsize = ext2_inode_setsize,
	.mode = ext2_inode_mode,
	.setmode = ext2_inode_setmode,
	.realdev = ext2_inode_realdev,
	.real_filename = ext2_inode_real_filename,
	.minode = ext2_inode_minode,
	.noitem = ext2_inode_noitem,
	.additem = ext2_inode_additem,
	.delitem = ext2_inode_delitem,
	.findson = ext2_inode_findson,
	.getuid = ext2_inode_getuid,
	.setuid = ext2_inode_setuid,
	.getgid = ext2_inode_getgid,
	.setgid = ext2_inode_setgid,
	.mknod = ext2_inode_mknod,
	.bmap = ext2_inode_bmap,
	.blocksize = ext2_inode_blocksize,
	.max_filesize = ext2_inode_max_filesize,
	.update = ext2_inode_update,
	.change_nlinks = ext2_inode_change_nlinks,
	.get_name_of_son = ext2_inode_get_name_of_son,
	.stat = ext2_inode_stat,
	.readdir = ext2_inode_readdir,
	.readlink = ext2_inode_readlink
};

static void ext2_inode_free(struct inode *inode)
{
	kfree(inode->i_data);
	inode->i_data = NULL;
}

static BOOLEAN ext2_inode_can_delete(struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

	if(!ei->ext2_raw_inode.i_links_count)
		return TRUE;

	return FALSE;
}

typedef struct {
  u32_t  *p;
  u32_t  key;
  struct buf_head *bh;
} Indirect;

static inline void add_chain(Indirect *p, struct buf_head *bh, u32_t *v)
{
  p->key = *(p->p = v);
  p->bh = bh;
}

static inline int verify_chain(Indirect *from, Indirect *to)
{
  while (from <= to && from->key == *from->p)
    from++;
  return (from > to);
}

/**
 *  ext2_block_to_path - parse the block number into array of offsets
 *  @inode: inode in question (we are only interested in its superblock)
 *  @i_block: block number to be parsed
 *  @offsets: array to store the offsets in
 *      @boundary: set this non-zero if the referred-to block is likely to be
 *             followed (on disk) by an indirect block.
 *  To store the locations of file's data ext2 uses a data structure common
 *  for UNIX filesystems - tree of pointers anchored in the inode, with
 *  data blocks at leaves and indirect blocks in intermediate nodes.
 *  This function translates the block number into path in that tree -
 *  return value is the path length and @offsets[n] is the offset of
 *  pointer to (n+1)th node in the nth one. If @block is out of range
 *  (negative or too large) warning is printed and zero returned.
 *
 *  Note: function doesn't find node addresses, so no IO is needed. All
 *  we need to know is the capacity of indirect blocks (taken from the
 *  inode->i_sb).
 */

/*
 * Portability note: the last comparison (check that we fit into triple
 * indirect block) is spelled differently, because otherwise on an
 * architecture with 32-bit longs and 8Kb pages we might get into trouble
 * if our filesystem had 8Kb blocks. We might use long long, but that would
 * kill us on x86. Oh, well, at least the sign propagation does not matter -
 * i_block would have to be negative in the very beginning, so we would not
 * get there at all.
 */
static int ext2_block_to_path(struct inode *inode,
      unsigned long i_block, int offsets[4], int *boundary)
{
  int ptrs = EXT2_ADDR_PER_BLOCK;
  int ptrs_bits = EXT2_ADDR_PER_BLOCK_BITS(inode->i_sb);
  const long direct_blocks = EXT2_NDIR_BLOCKS,
    indirect_blocks = ptrs,
    double_blocks = (1 << (ptrs_bits * 2));
  int n = 0;
  int final = 0;



  if (i_block < 0) {
    printk("warning: %s %s: block < 0\n", __func__,__FILE__);
		BUG();
  } else if (i_block < direct_blocks) {
    offsets[n++] = i_block;
    final = direct_blocks;
  } else if ( (i_block -= direct_blocks) < indirect_blocks) {
    offsets[n++] = EXT2_IND_BLOCK;
    offsets[n++] = i_block;
    final = ptrs;
  } else if ((i_block -= indirect_blocks) < double_blocks) {
    offsets[n++] = EXT2_DIND_BLOCK;
    offsets[n++] = i_block >> ptrs_bits;
    offsets[n++] = i_block & (ptrs - 1);
    final = ptrs;
  } else if (((i_block -= double_blocks) >> (ptrs_bits * 2)) < ptrs) {
    offsets[n++] = EXT2_TIND_BLOCK;
    offsets[n++] = i_block >> (ptrs_bits * 2);
    offsets[n++] = (i_block >> ptrs_bits) & (ptrs - 1);
    offsets[n++] = i_block & (ptrs - 1);
    final = ptrs;
  } else {
    printk("warning: %s %s: block is too big", __func__,__FILE__);
		BUG();
  }


  if (boundary)
    *boundary = final - 1 - (i_block & (ptrs - 1));

  return n;
}

/**
 *  ext2_free_data - free a list of data blocks
 *  @inode: inode we are dealing with
 *  @p: array of block numbers
 *  @q: points immediately past the end of array
 *
 *  We are freeing all blocks refered from that array (numbers are
 *  stored as little-endian 32-bit) and updating @inode->i_blocks
 *  appropriately.
 */
extern void ext2_free_blocks(struct inode *inode,unsigned long block,unsigned count);
static inline void ext2_free_data(struct inode *inode, u32_t *p, u32_t *q)
{
  unsigned long block_to_free = 0, count = 0;
  unsigned long nr;

  for ( ; p < q ; p++) {
    nr = le32_to_cpu(*p);
    if (nr) {
      *p = 0;
      /* accumulate blocks to free if they're contiguous */
      if (count == 0)
        goto free_this;
      else if (block_to_free == nr - count)
        count++;
      else {
        ext2_free_blocks (inode, block_to_free, count);
      free_this:
        block_to_free = nr;
        count = 1;
      }
    }
  }
  if (count > 0) {
    ext2_free_blocks (inode, block_to_free, count);
  }
}

/**
 *  ext2_get_branch - read the chain of indirect blocks leading to data
 *  @inode: inode in question
 *  @depth: depth of the chain (1 - direct pointer, etc.)
 *  @offsets: offsets of pointers in inode/indirect blocks
 *  @chain: place to store the result
 *  @err: here we store the error value
 *
 *  Function fills the array of triples <key, p, bh> and returns %NULL
 *  if everything went OK or the pointer to the last filled triple
 *  (incomplete one) otherwise. Upon the return chain[i].key contains
 *  the number of (i+1)-th block in the chain (as it is stored in memory,
 *  i.e. little-endian 32-bit), chain[i].p contains the address of that
 *  number (it points into struct inode for i==0 and into the bh->b_data
 *  for i>0) and chain[i].bh points to the buffer_head of i-th indirect
 *  block for i>0 and NULL for i==0. In other words, it holds the block
 *  numbers of the chain, addresses they were taken from (and where we can
 *  verify that chain did not change) and buffer_heads hosting these
 *  numbers.
 *
 *  Function stops when it stumbles upon zero pointer (absent block)
 *    (pointer to last triple returned, *@err == 0)
 *  or when it gets an IO error reading an indirect block
 *    (ditto, *@err == -EIO)
 *  or when it notices that chain had been changed while it was reading
 *    (ditto, *@err == -EAGAIN)
 *  or when it reads all @depth-1 indirect blocks successfully and finds
 *  the whole chain, all way to the data (returns %NULL, *err == 0).
 */
static Indirect *ext2_get_branch(struct inode *inode,
         int depth,
         int *offsets,
         Indirect chain[4],
         int *err)
{
  struct super_block *sb = inode->i_sb;
  Indirect *p = chain;
  struct buf_head *bh;

  *err = 0;
  /* i_data is not going away, no lock needed */
  add_chain (chain, NULL, EXT2_I(inode)->I_data + *offsets);

  if (!p->key)
    goto no_block;
  while (--depth) {

    bh = sd_bread(sb->s_dev, p->key*EXT2_BLOCK_GRAN);
    if (!bh)
      goto failure;
    if (!verify_chain(chain, p))
      goto changed;

    add_chain(++p, bh, (u32_t*)bh->b_data + *++offsets);
    if (!p->key)
      goto no_block;
  }
  return NULL;

changed:
  brelse(bh);
  *err = -EAGAIN;
  goto no_block;
failure:
  *err = -EIO;
no_block:
  return p;
}

/*
 * Probably it should be a library function... search for first non-zero word
 * or memcmp with zero_page, whatever is better for particular architecture.
 * Linus?
 */
static inline int all_zeroes(u32_t *p, u32_t *q)
{
  while (p < q)
    if (*p++)
      return 0;
  return 1;
}

/**
 *  ext2_find_shared - find the indirect blocks for partial truncation.
 *  @inode:   inode in question
 *  @depth:   depth of the affected branch
 *  @offsets: offsets of pointers in that branch (see ext2_block_to_path)
 *  @chain:   place to store the pointers to partial indirect blocks
 *  @top:   place to the (detached) top of branch
 *
 *  This is a helper function used by ext2_truncate().
 *
 *  When we do truncate() we may have to clean the ends of several indirect
 *  blocks but leave the blocks themselves alive. Block is partially
 *  truncated if some data below the new i_size is refered from it (and
 *  it is on the path to the first completely truncated data block, indeed).
 *  We have to free the top of that path along with everything to the right
 *  of the path. Since no allocation past the truncation point is possible
 *  until ext2_truncate() finishes, we may safely do the latter, but top
 *  of branch may require special attention - pageout below the truncation
 *  point might try to populate it.
 *
 *  We atomically detach the top of branch from the tree, store the block
 *  number of its root in *@top, pointers to buffer_heads of partially
 *  truncated blocks - in @chain[].bh and pointers to their last elements
 *  that should not be removed - in @chain[].p. Return value is the pointer
 *  to last filled element of @chain.
 *
 *  The work left to caller to do the actual freeing of subtrees:
 *    a) free the subtree starting from *@top
 *    b) free the subtrees whose roots are stored in
 *      (@chain[i].p+1 .. end of @chain[i].bh->b_data)
 *    c) free the subtrees growing from the inode past the @chain[0].p
 *      (no partially truncated stuff there).
 */
static Indirect *ext2_find_shared(struct inode *inode,
        int depth,
        int offsets[4],
        Indirect chain[4],
        u32_t *top)
{
  Indirect *partial, *p;
  int k, err;

  *top = 0;
  for (k = depth; k > 1 && !offsets[k-1]; k--)
    ;
  partial = ext2_get_branch(inode, k, offsets, chain, &err);
  if (!partial)
    partial = chain + k-1;
  /*
   * If the branch acquired continuation since we've looked at it -
   * fine, it should all survive and (new) top doesn't belong to us.
   */
  if (!partial->key && *partial->p) {
    goto no_top;
  }
  for (p=partial; p>chain && all_zeroes((u32_t*)p->bh->b_data,p->p); p--)
    ;
  /*
   * OK, we've found the last block that must survive. The rest of our
   * branch should be detached before unlocking. However, if that rest
   * of branch is all ours and does not grow immediately from the inode
   * it's easier to cheat and just decrement partial->p.
   */
  if (p == chain + k - 1 && p > chain) {
    p->p--;
  } else {
    *top = *p->p;
    *p->p = 0;
  }

  while(partial > p)
  {
    brelse(partial->bh);
    partial--;
  }
no_top:
  return partial;
}

/**
 *  ext2_free_branches - free an array of branches
 *  @inode: inode we are dealing with
 *  @p: array of block numbers
 *  @q: pointer immediately past the end of array
 *  @depth: depth of the branches to free
 *
 *  We are freeing all blocks refered from these branches (numbers are
 *  stored as little-endian 32-bit) and updating @inode->i_blocks
 *  appropriately.
 */
static void ext2_free_branches(struct inode *inode, u32_t *p, u32_t *q, int depth)
{
  struct buf_head * bh;
  unsigned long nr;

  if (depth--) {
    int addr_per_block = EXT2_ADDR_PER_BLOCK;
    for ( ; p < q ; p++) {
      nr = le32_to_cpu(*p);
      if (!nr)
        continue;
      *p = 0;
      bh = sd_bread(inode->i_sb->s_dev, nr*EXT2_BLOCK_GRAN);
      /*
       * A read failure? Report error and clear slot
       * (should be rare).
       */
      if (!bh) {
        printk("ext2_free_branches",
          "Read failure, inode=%ld, block=%ld",
          inode->i_num, nr);
        continue;
      }
      ext2_free_branches(inode,
             (u32_t*)bh->b_data,
             (u32_t*)bh->b_data + addr_per_block,
             depth);
			/*
			 *Discard this buffer.
			 */
      //bforget(bh);
			bh->b_flags &= ~B_DIRTY;
			brelse(bh);
      ext2_free_blocks(inode, nr, 1);
    }
  } else
    ext2_free_data(inode, p, q);
}

      
extern void ext2_discard_reservation(struct inode *inode);
static void ext2_truncate (struct inode *inode)
{
	struct ext2_inode_info *ei = EXT2_I(inode);
  u32_t *i_Data = ei->I_data;
  int addr_per_block = EXT2_ADDR_PER_BLOCK;
  int offsets[4];
  Indirect chain[4];
  Indirect *partial;
  u32_t nr = 0; 
  int n;
  long iblock;
  unsigned blocksize;


  if (!(S_ISREG(ei->ext2_raw_inode.i_mode) || S_ISDIR(ei->ext2_raw_inode.i_mode) ||
      S_ISLNK(ei->ext2_raw_inode.i_mode))){
		printk("Trying to truncate files which are not truncatable. %s %s\n",
			__func__,__FILE__);
		BUG();
	}

  blocksize = EXT2_BLOCK_SIZE; 
  iblock = (ei->i_size + blocksize-1)
          >> EXT2_BLOCK_BITS;

  n = ext2_block_to_path(inode, iblock, offsets, NULL);
  if (n == 0)
    return;

  if (n == 1) {
    ext2_free_data(inode, i_Data+offsets[0],
          i_Data + EXT2_NDIR_BLOCKS);
    goto do_indirects;
  }

  partial = ext2_find_shared(inode, n, offsets, chain, &nr);
  /* Kill the top of shared branch (already detached) */
  if (nr) {
    if (partial == chain)
      ;//mark_inode_dirty(inode);
    else
      partial->bh->b_flags |= B_DIRTY; //mark_buffer_dirty_inode(partial->bh, inode);
    ext2_free_branches(inode, &nr, &nr+1, (chain+n-1) - partial);
  }
  /* Clear the ends of indirect blocks on the shared branch */
  while (partial > chain) {
    ext2_free_branches(inode,
           partial->p + 1,
           (u32_t*)partial->bh->b_data+addr_per_block,
           (chain+n-1) - partial);
    //mark_buffer_dirty_inode(partial->bh, inode);
		partial->bh->b_flags |= B_DIRTY;
    brelse (partial->bh);
    partial--;
  }
do_indirects:
  /* Kill the remaining (whole) subtrees */
  switch (offsets[0]) {
    default:
      nr = i_Data[EXT2_IND_BLOCK];
      if (nr) {
        i_Data[EXT2_IND_BLOCK] = 0;
        ext2_free_branches(inode, &nr, &nr+1, 1);
      }
    case EXT2_IND_BLOCK:
      nr = i_Data[EXT2_DIND_BLOCK];
      if (nr) {
        i_Data[EXT2_DIND_BLOCK] = 0;
        ext2_free_branches(inode, &nr, &nr+1, 2);
      }
    case EXT2_DIND_BLOCK:
      nr = i_Data[EXT2_TIND_BLOCK];
      if (nr) {
        i_Data[EXT2_TIND_BLOCK] = 0;
        ext2_free_branches(inode, &nr, &nr+1, 3);
      }
    case EXT2_TIND_BLOCK:
      ;
  }

  ext2_discard_reservation(inode);

  EXT2_I(inode)->ext2_raw_inode.i_mtime = curclock();
	EXT2_I(inode)->ext2_raw_inode.i_ctime = curclock();
}

static int ext2_inode_truncate(struct inode *inode, loff_t new_size)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;


	if(unlikely(ei->i_size < new_size)){
		printk("No truncate needed here. %s %s\n",__func__,__FILE__);
		BUG();
	}

	if(ei->i_size == new_size)
		return 0;

	ei->i_size = new_size;
	if(ei->ext2_raw_inode.i_blocks)
		ext2_truncate(inode);	

	return 0;
}

static loff_t ext2_inode_size(struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;
	
	return ei->i_size;
}

static void ext2_inode_setsize(struct inode *inode, loff_t new_size)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

	ei->i_size = new_size;
}

static mode_t ext2_inode_mode(struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

	return ei->ext2_raw_inode.i_mode;
}

static void ext2_inode_setmode(struct inode *inode, mode_t mode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

	ei->ext2_raw_inode.i_mode = mode;
}

static dev_t ext2_inode_realdev(struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

	return ei->ext2_raw_inode.i_block[0];
}


static BOOLEAN ext2_inode_real_filename(char * page, struct inode *inode, int * error)
{
	struct ext2_inode_info *ei = inode->i_data;
	char *link = (char*)ei->I_data;
	int fsize = (int)ei->i_size;

	if(unlikely(fsize > EXT2_LINK_LEN)) {
		printk("a long ext2 symbolic link detected. %s %s \n",
			__func__,__FILE__);
		BUG();
	}
	memcpy(page,link,fsize);
	*(page+fsize) = 0;

	return TRUE;
}

static BOOLEAN ext2_inode_minode(struct inode *inode, off_t off, unsigned long b)
{
	printk("ext2_inode_minode not implemented yet. %s\n",__FILE__);
	BUG();
	return TRUE;
}

/*
 * Return the offset into page `page_nr' of the last valid
 * byte in that page, plus one.
 */
static unsigned
ext2_last_byte(struct ext2_inode_info *inode, unsigned long page_nr)
{
  unsigned last_byte = (unsigned) inode->i_size;

  last_byte -= page_nr << EXT2_BLOCK_BITS;
  if (last_byte > EXT2_BLOCK_SIZE)
    last_byte = EXT2_BLOCK_SIZE;
  return last_byte;
}

static BOOLEAN ext2_inode_noitem(struct inode *dir)
{
	struct ext2_inode_info *ei = EXT2_I(dir);
	struct ext2_dirent *ent=NULL;
	struct buf_head *bh;
	loff_t pos = 0;
	ext2_fsblk_t block = 0;
	u8_t*kaddr;

	for(pos = 0; pos<ei->i_size; pos += EXT2_BLOCK_SIZE){
		block = ext2_inode_bmap(dir,pos);
		if(unlikely(block == NOBLK || block == 0)){
			printk("bmap error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		bh = sd_bread(dir->i_dev,block*EXT2_BLOCK_GRAN);
		if(!bh){
			printk("sd_bread error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		
		kaddr = bh->b_data;
		ent = (struct ext2_dirent *)kaddr;
		kaddr += ext2_last_byte(ei,pos>>EXT2_BLOCK_BITS);
		while((u8_t*)ent < kaddr){
			if(ent->rec_len == 0){
				printk("Invalid dir entry. \n");
				BUG();
			}

			if(ent->inode && 
				 !( (ent->name_len==1) && (ent->name[0]=='.') ) && 
				 !( (ent->name_len==2) && !strncmp("..",ent->name,2) )){
				brelse(bh);
				return FALSE;
			}
			ent = ext2_next_entry(ent);
		}
		brelse(bh);
	}
	return TRUE;
}

#define S_SHIFT 12
static unsigned char ext2_type_by_mode[S_IFMT >> S_SHIFT] = {
  [S_IFREG >> S_SHIFT]  = EXT2_FT_REG_FILE,
  [S_IFDIR >> S_SHIFT]  = EXT2_FT_DIR,
  [S_IFCHR >> S_SHIFT]  = EXT2_FT_CHRDEV,
  [S_IFBLK >> S_SHIFT]  = EXT2_FT_BLKDEV,
  [S_IFIFO >> S_SHIFT]  = EXT2_FT_FIFO,
  [S_IFSOCK >> S_SHIFT] = EXT2_FT_SOCK,
  [S_IFLNK >> S_SHIFT]  = EXT2_FT_SYMLINK,
};

static inline void ext2_set_de_type(struct ext2_dirent *de, struct inode *inode)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;
  mode_t mode = ei->ext2_raw_inode.i_mode;
  if (EXT2_HAS_INCOMPAT_FEATURE(EXT2_SB(inode->i_sb), EXT2_FEATURE_INCOMPAT_FILETYPE))
    de->file_type = ext2_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
  else
    de->file_type = 0;
}

static BOOLEAN ext2_inode_additem(struct inode *dir, const char *name, int *error, struct inode *inode)
{
	struct ext2_inode_info *ei = EXT2_I(dir);
	ext2_fsblk_t block = 0;
	loff_t pos = 0;
	int namelen = strlen(name);
	int reclen = EXT2_DIR_REC_LEN(namelen);
	struct buf_head *bh=NULL;
	u8_t *kaddr;
	struct ext2_dirent *ent=NULL;
	int name_len = 0;
	int rec_len = 0;
	int expand = 0;

	//printk("file size: %d add item: %s\n",(unsigned)ei->i_size,name);

	for(pos = 0; pos<=ei->i_size;pos += EXT2_BLOCK_SIZE){
		u8_t *dir_end;

		block = ext2_inode_bmap(dir,pos);
		if(unlikely(block == NOBLK || block == 0)){
			printk("bmap error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		bh = sd_bread(dir->i_dev,block * EXT2_BLOCK_GRAN);
		if(!bh){
			printk("sd_bread error. %s %s\n",__func__,__FILE__);
			BUG();
		}

		if(unlikely(expand)){
			printk("%s %s\n",__func__,__FILE__);
			BUG();
		}else if(pos == ei->i_size)
			expand = 1;

		kaddr = bh->b_data;
		dir_end = kaddr + ext2_last_byte(ei,pos>>EXT2_BLOCK_BITS);
		ent = (struct ext2_dirent *)kaddr;
		kaddr += EXT2_BLOCK_SIZE - reclen;
		while((u8_t*)ent <= kaddr){
      if ((u8_t*)ent == dir_end) {
        /* We hit i_size */
				name_len = 0;
				//rec_len = EXT2_DIRENT_CHUNK_SIZE;
				rec_len = EXT2_BLOCK_SIZE;
        //ent->rec_len = EXT2_DIRENT_CHUNK_SIZE; 
        ent->rec_len = EXT2_BLOCK_SIZE; 
        ent->inode = 0;
        goto got_it;
      }
      if (ent->rec_len == 0) {
				printk("zero length directory entry. %s %s\n",
					__func__,__FILE__);
        *error = -EIO;
				brelse(bh);
        goto err_out;
      }
			if(ent->inode && (namelen==ent->name_len) &&
					!strncmp(name,ent->name,namelen)){
				printk("Adding an existant entry to a directory. %s %s\n",
					__func__,__FILE__);
				brelse(bh);
				goto err_out;
			}
      name_len = EXT2_DIR_REC_LEN(ent->name_len);
      rec_len = ext2_rec_len_from_disk(ent->rec_len);
      if (!ent->inode && rec_len >= reclen)
        goto got_it;
      if (rec_len >= name_len + reclen)
        goto got_it;

			ent = (struct ext2_dirent *) ((char *) ent + rec_len);
		}
		brelse(bh);
	}
got_it:
	if(ent->inode){
    struct ext2_dirent *de1 = (struct ext2_dirent *) ((char *) ent + name_len);
    de1->rec_len = ext2_rec_len_to_disk(rec_len - name_len);
    ent->rec_len = ext2_rec_len_to_disk(name_len);
    ent = de1;
	}

  ent->name_len = namelen;
  memcpy(ent->name, name, namelen);
  ent->inode = inode->i_num;
  ext2_set_de_type (ent, inode);
  ei->ext2_raw_inode.i_mtime = ei->ext2_raw_inode.i_ctime = curclock();
  EXT2_I(dir)->i_flags &= ~EXT2_BTREE_FL;
	if(expand)
		ei->i_size += EXT2_BLOCK_SIZE;

	bh->b_flags |= B_DIRTY;
	brelse(bh);
	return TRUE;
err_out: 
	return FALSE;
}

static BOOLEAN ext2_inode_delitem(struct inode *inode, const char *name, int *error)
{
	struct ext2_inode_info *ei = EXT2_I(inode);
	ext2_fsblk_t block = 0;
	loff_t pos = 0;
	int namelen = strlen(name);
	int reclen = EXT2_DIR_REC_LEN(namelen);
	struct buf_head *bh=NULL;
	u8_t *kaddr;
	struct ext2_dirent *ent=NULL;
	struct ext2_dirent *pre=NULL;
	int rec_len = 0;

	//printk("file size: %d del item: %s\n",(unsigned)ei->i_size,name);

	if(!S_ISDIR(ei->ext2_raw_inode.i_mode)){
		printk("inoptr must be a directory %s %s\n",__func__,__FILE__);
		BUG();
	}

	if(inode->i_sb->s_roflag){
		*error = -EROFS;
		goto err_out;
	}

	if(!strncmp(name, ".", namelen)
		|| !strncmp(name, "..", namelen)){
		*error = -EPERM;
		goto err_out;
	}

	for(pos = 0; pos<ei->i_size;pos += EXT2_BLOCK_SIZE){
		u8_t *dir_end;

		block = ext2_inode_bmap(inode,pos);
		if(unlikely(block == NOBLK || block == 0)){
			printk("bmap error. %s %s\n",__func__,__FILE__);
			BUG();
		}

		bh = sd_bread(inode->i_dev,block * EXT2_BLOCK_GRAN);
		if(!bh){
			printk("sd_bread error. %s %s\n",__func__,__FILE__);
			BUG();
		}

		kaddr = bh->b_data;
		dir_end = kaddr + ext2_last_byte(ei,pos>>EXT2_BLOCK_BITS);
		ent = (struct ext2_dirent *)kaddr;
		kaddr += EXT2_BLOCK_SIZE - reclen;
		pre = NULL;
		while((u8_t*)ent <= kaddr){
      if ((u8_t*)ent == dir_end) {
				printk("Invalid execution path? %s %s\n",__func__,__FILE__);
				BUG();
				*error = -ENOENT;
				brelse(bh);
				goto err_out;
      }

      if (ent->rec_len == 0) {
				printk("zero length directory entry. %s %s\n",
					__func__,__FILE__);
				BUG();
        *error = -EIO;
				brelse(bh);
        goto err_out;
      }

			if(ent->inode && (namelen==ent->name_len) &&
					!strncmp(name,ent->name,namelen)){
				ent->inode = 0;
				//do our best to merge entries
				if(pre){
					//printk("merged on deletion.\n");
      		rec_len = ext2_rec_len_from_disk(ent->rec_len);
					pre->rec_len += rec_len;
				}
				bh->b_flags |= (B_DIRTY | B_DONE);
				brelse(bh);
				return TRUE;
			}
      rec_len = ext2_rec_len_from_disk(ent->rec_len);
			pre = ent;
			ent = (struct ext2_dirent *) ((char *) ent + rec_len);
		}
		brelse(bh);
	}
	*error = -ENOENT;
err_out: 
	return FALSE;
}

static ino_t ext2_inode_findson(struct inode *dir, const char *name)
{
	int namelen = strlen(name);
	unsigned reclen = EXT2_DIR_REC_LEN(namelen);
	struct ext2_inode_info *ei = EXT2_I(dir);
	struct ext2_dirent *ent=NULL;
	struct buf_head *bh;
	loff_t pos = 0;
	ext2_fsblk_t block = 0;
	u8_t*kaddr;

#if 0
	int flag = 0;
	if(!strcmp(name,".a.swp"))
		flag = 1;
#endif

	for(pos = 0; pos<ei->i_size; pos += EXT2_BLOCK_SIZE){
		block = ext2_inode_bmap(dir,pos);
		if(unlikely(block == NOBLK || block == 0)){
			printk("bmap error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		bh = sd_bread(dir->i_dev,block*EXT2_BLOCK_GRAN);
		if(!bh){
			printk("sd_bread error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		
		kaddr = bh->b_data;
		ent = (struct ext2_dirent *)kaddr;
		kaddr += ext2_last_byte(ei,pos>>EXT2_BLOCK_BITS) - reclen;
		while((u8_t*)ent <= kaddr){
			if(ent->rec_len == 0){
				printk("Invalid dir entry. \n");
				BUG();
			}
#if 0
			if(flag ==1 )
				printk("ent->name: %s\n",ent->name);
#endif

			if(ent->inode && (namelen == ent->name_len) && 
					!strncmp(name,ent->name,namelen)){
				brelse(bh);
				goto found;
			}
			ent = ext2_next_entry(ent);
		}
		brelse(bh);
	}	
	//printk("failed to find: %s from inode: %x\n",name,dir);
	return NOINO;
found:
	return ent->inode;
}

static uid_t ext2_inode_getuid(struct inode * inoptr)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inoptr->i_data;

	return ei->ext2_raw_inode.i_uid;
}

static void ext2_inode_setuid(struct inode *inoptr, uid_t uid)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inoptr->i_data;

	ei->ext2_raw_inode.i_uid = uid;
}

static gid_t ext2_inode_getgid(struct inode *inoptr)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inoptr->i_data;

	return ei->ext2_raw_inode.i_gid;
}

static void ext2_inode_setgid(struct inode *inoptr, gid_t gid)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inoptr->i_data;

	ei->ext2_raw_inode.i_gid = gid;
}

static void ext2_inode_mknod(struct inode *inode, dev_t dev)
{
	printk("ext2_inode_mknod not implemented yet. %s\n",__FILE__);
	BUG();
}

/**
 *  ext2_find_near - find a place for allocation with sufficient locality
 *  @inode: owner
 *  @ind: descriptor of indirect block.
 *
 *  This function returns the preferred place for block allocation.
 *  It is used when heuristic for sequential allocation fails.
 *  Rules are:
 *    + if there is a block to the left of our position - allocate near it.
 *    + if pointer will live in indirect block - allocate near that block.
 *    + if pointer will live in inode - allocate in the same cylinder group.
 *
 * In the latter case we colour the starting block by the callers PID to
 * prevent it from clashing with concurrent allocations for a different inode
 * in the same block group.   The PID is used here so that functionally related
 * files will be close-by on-disk.
 *
 *  Caller must make sure that @ind is valid and will stay that way.
 */

static ext2_fsblk_t ext2_find_near(struct inode *inode, Indirect *ind)
{
  struct ext2_inode_info *ei = EXT2_I(inode);
  u32_t *start = ind->bh ? (u32_t *) ind->bh->b_data : ei->I_data;
  u32_t *p;
  ext2_fsblk_t bg_start;
  ext2_fsblk_t colour;

  /* Try to find previous block */
  for (p = ind->p - 1; p >= start; p--)
    if (*p)
      return le32_to_cpu(*p);

  /* No such thing, so let's try location of indirect block */
  if (ind->bh)
    return ind->bh->b_blocknr;

  /*
   * It is going to be refered from inode itself? OK, just put it into
   * the same cylinder group then.
   */
  bg_start = ext2_group_first_block_no(EXT2_SB(inode->i_sb), ei->i_block_group);
  colour = (current->pid % 16) *
      (EXT2_BLOCKS_PER_GROUP(inode->i_sb) / 16); 
  return bg_start + colour;
}

/**
 *  ext2_find_goal - find a preferred place for allocation.
 *  @inode: owner
 *  @block:  block we want
 *  @partial: pointer to the last triple within a chain
 *
 *  Returns preferred place for a block (the goal).
 */

static inline ext2_fsblk_t ext2_find_goal(struct inode *inode, long block,
            Indirect *partial)
{
  struct ext2_block_alloc_info *block_i;

  block_i = EXT2_I(inode)->i_block_alloc_info;

  /*
   * try the heuristic for sequential allocation,
   * failing that at least try to get decent locality.
   */
  if (block_i && (block == block_i->last_alloc_logical_block + 1) 
    && (block_i->last_alloc_physical_block != 0)) {
    return block_i->last_alloc_physical_block + 1; 
  }

  return ext2_find_near(inode, partial);
}

/**
 *  ext2_blks_to_allocate: Look up the block map and count the number
 *  of direct blocks need to be allocated for the given branch.
 *
 *  @branch: chain of indirect blocks
 *  @k: number of blocks need for indirect blocks
 *  @blks: number of data blocks to be mapped.
 *  @blocks_to_boundary:  the offset in the indirect block
 *
 *  return the total number of blocks to be allocate, including the
 *  direct and indirect blocks.
 */
static int
ext2_blks_to_allocate(Indirect * branch, int k, unsigned long blks,
    int blocks_to_boundary)
{
  unsigned long count = 0;

  /*
   * Simple case, [t,d]Indirect block(s) has not allocated yet
   * then it's clear blocks on that path have not allocated
   */
  if (k > 0) {
    /* right now don't hanel cross boundary allocation */
    if (blks < blocks_to_boundary + 1)
      count += blks;
    else
      count += blocks_to_boundary + 1;
    return count;
  }

  count++;
  while (count < blks && count <= blocks_to_boundary
    && le32_to_cpu(*(branch[0].p + count)) == 0) {
    count++;
  }
  return count;
}

/**
 *  ext2_alloc_blocks: multiple allocate blocks needed for a branch
 *  @indirect_blks: the number of blocks need to allocate for indirect
 *      blocks
 *
 *  @new_blocks: on return it will store the new block numbers for
 *  the indirect blocks(if needed) and the first direct block,
 *  @blks:  on return it will store the total number of allocated
 *    direct blocks
 */
static int ext2_alloc_blocks(struct inode *inode,
      ext2_fsblk_t goal, int indirect_blks, int blks,
      ext2_fsblk_t new_blocks[4], int *err)
{
  int target, i;
  unsigned long count = 0;
  int index = 0;
  ext2_fsblk_t current_block = 0;
  int ret = 0;

  /*
   * Here we try to allocate the requested multiple blocks at once,
   * on a best-effort basis.
   * To build a branch, we should allocate blocks for
   * the indirect blocks(if not allocated yet), and at least
   * the first direct block of this branch.  That's the
   * minimum number of blocks need to allocate(required)
   */
  target = blks + indirect_blks;

  while (1) {
    count = target;

    /* allocating blocks for indirect blocks and direct blocks */
    current_block = ext2_new_blocks(inode,goal,&count);
    if (*err){
			printk("allocate blocks failed. %s %s\n",__func__,__FILE__);
			BUG();
      goto failed_out;
		}

    target -= count;
    /* allocate blocks for indirect blocks */
    while (index < indirect_blks && count) {
      new_blocks[index++] = current_block++;
      count--;
    }

    if (count > 0)
      break;
  }

  /* save the new block number for the first direct block */
  new_blocks[index] = current_block;

  /* total number of blocks allocated for direct blocks */
  ret = count;
  *err = 0;
  return ret;
failed_out:
  for (i = 0; i <index; i++)
    ext2_free_blocks(inode, new_blocks[i], 1);
  return ret;
}

/**
 *  ext2_alloc_branch - allocate and set up a chain of blocks.
 *  @inode: owner
 *  @num: depth of the chain (number of blocks to allocate)
 *  @offsets: offsets (in the blocks) to store the pointers to next.
 *  @branch: place to store the chain in.
 *
 *  This function allocates @num blocks, zeroes out all but the last one,
 *  links them into chain and (if we are synchronous) writes them to disk.
 *  In other words, it prepares a branch that can be spliced onto the
 *  inode. It stores the information about that chain in the branch[], in
 *  the same format as ext2_get_branch() would do. We are calling it after
 *  we had read the existing part of chain and partial points to the last
 *  triple of that (one with zero ->key). Upon the exit we have the same
 *  picture as after the successful ext2_get_block(), excpet that in one
 *  place chain is disconnected - *branch->p is still zero (we did not
 *  set the last link), but branch->key contains the number that should
 *  be placed into *branch->p to fill that gap.
 *
 *  If allocation fails we free all blocks we've allocated (and forget
 *  their buffer_heads) and return the error value the from failed
 *  ext2_alloc_block() (normally -ENOSPC). Otherwise we set the chain
 *  as described above and return 0.
 */

extern sector_t locate_block(dev_t dev, sector_t blk);
static int ext2_alloc_branch(struct inode *inode,
      int indirect_blks, int *blks, ext2_fsblk_t goal,
      int *offsets, Indirect *branch)
{
  int blocksize =	EXT2_BLOCK_SIZE; 
  int i, n = 0;
  int err = 0;
  struct buf_head *bh;
  int num;
  ext2_fsblk_t new_blocks[4];
  ext2_fsblk_t current_block;

 
 	num = ext2_alloc_blocks(inode, goal, indirect_blks,
        *blks, new_blocks, &err);


  if (err)
    return err;


  branch[0].key = cpu_to_le32(new_blocks[0]);
  /*
   * metadata blocks and data blocks are allocated.
   */
  for (n = 1; n <= indirect_blks;  n++) {
    /*
     * Get buffer_head for parent block, zero it out
     * and set the pointer to new one, then send
     * parent to disk.
     */
		//sector_t new_blk = locate_block(inode->i_sb->s_dev,
		//												(sector_t)(new_blocks[n-1]) * EXT2_BLOCK_GRAN);
		//printk("new_blk: %u %u\n",new_blocks[n-1],(unsigned)new_blk);
    //bh = getblk(inode->i_sb->s_dev,new_blk,EXT2_BLOCK_SIZE);
		bh = sd_bread(inode->i_sb->s_dev,new_blocks[n-1]*EXT2_BLOCK_GRAN);
    branch[n].bh = bh;
    memset(bh->b_data, 0, blocksize);
    branch[n].p = (u32_t *) bh->b_data + offsets[n];
    branch[n].key = cpu_to_le32(new_blocks[n]);
    *branch[n].p = branch[n].key;

    if ( n == indirect_blks) {
      current_block = new_blocks[n];
      /*
       * End of chain, update the last new metablock of
       * the chain to point to the new allocated
       * data blocks numbers
       */
      for (i=1; i < num; i++)
        *(branch[n].p + i) = cpu_to_le32(++current_block);
    }
		bh->b_flags |= B_DIRTY;
  }
  *blks = num;
  return err;
}

/**
 * ext2_splice_branch - splice the allocated branch onto inode.
 * @inode: owner
 * @block: (logical) number of block we are adding
 * @where: location of missing link
 * @num:   number of indirect blocks we are adding
 * @blks:  number of direct blocks we are adding
 *
 * This function fills the missing link and does all housekeeping needed in
 * inode (->i_blocks, etc.). In case of success we end up with the full
 * chain to new block and return 0.
 */
static void ext2_splice_branch(struct inode *inode,
      long block, Indirect *where, int num, int blks)
{
  int i;
  struct ext2_block_alloc_info *block_i;
  ext2_fsblk_t current_block;
	struct ext2_inode_info *ei = (struct ext2_inode_info*)inode->i_data;

  block_i = EXT2_I(inode)->i_block_alloc_info;

  /* XXX LOCKING probably should have i_meta_lock ?*/
  /* That's it */

  *where->p = where->key;

  /*
   * Update the host buffer_head or inode to point to more just allocated
   * direct blocks blocks
   */
  if (num == 0 && blks > 1) {
    current_block = le32_to_cpu(where->key) + 1;
    for (i = 1; i < blks; i++)
      *(where->p + i ) = cpu_to_le32(current_block++);
  }

  /*
   * update the most recently allocated logical & physical block
   * in i_block_alloc_info, to assist find the proper goal block for next
   * allocation
   */
  if (block_i) {
    block_i->last_alloc_logical_block = block + blks - 1;
    block_i->last_alloc_physical_block =
        le32_to_cpu(where[num].key) + blks - 1;
  }

  /* We are done with atomic stuff, now do the rest of housekeeping */

  /* had we spliced it onto indirect block? */
  if (where->bh){
		where->bh->b_flags |= B_DIRTY;
	}

	ei->ext2_raw_inode.i_ctime = curclock();
}

/*
 * Allocation strategy is simple: if we have to allocate something, we will
 * have to go the whole way to leaf. So let's do it before attaching anything
 * to tree, set linkage between the newborn blocks, write them if sync is
 * required, recheck the path, free and repeat if check fails, otherwise
 * set the last missing link (that will protect us from any truncate-generated
 * removals - all blocks on the path are immune now) and possibly force the
 * write on the parent block.
 * That has a nice additional property: no special recovery from the failed
 * allocations is needed - we simply release blocks and do not touch anything
 * reachable from inode.
 *
 * `handle' can be NULL if create == 0.
 *
 * return > 0, # of blocks mapped or allocated.
 * return = 0, if plain lookup failed.
 * return < 0, error case.
 */
static unsigned long ext2_get_blocks(struct inode *inode,
			   unsigned long iblock, unsigned long maxblocks,
			   int create)
{
	int err = -EIO;
	int offsets[4];
	Indirect chain[4];
	Indirect *partial=NULL;
	ext2_fsblk_t goal;
	int indirect_blks;
	int blocks_to_boundary = 0;
	int depth;
	struct ext2_inode_info *ei = EXT2_I(inode);
	int count = 0;
	ext2_fsblk_t first_block = 0;
	unsigned long ret_block = 0;

	depth = ext2_block_to_path(inode,iblock,offsets,&blocks_to_boundary);

	if (depth == 0){
		printk("disk i/o error. %s %s\n",__func__,__FILE__);
		BUG();
		//return (err);
	}

	partial = ext2_get_branch(inode, depth, offsets, chain, &err);

	/* Simplest case - block found, no allocation needed */
	if (!partial) {

		first_block = le32_to_cpu(chain[depth - 1].key);
		count++;
		/*map more blocks*/
		while (count < maxblocks && count <= blocks_to_boundary) {
			ext2_fsblk_t blk;

			if (!verify_chain(chain, chain + depth - 1)) {
				/*
				 * Indirect block might be removed by
				 * truncate while we were reading it.
				 * Handling of that case: forget what we've
				 * got now, go to reread.
				 */
				err = -EAGAIN;
				count = 0;
				break;
			}
			blk = le32_to_cpu(*(chain[depth-1].p + count));
			if (blk == first_block + count)
				count++;
			else
				break;
		}
		if (err != -EAGAIN)
			goto got_it;
	}

	/* Next simple case - plain lookup or failed read of indirect block */
	if (!create || err == -EIO){
		printk("bmap failed. %s %s\n",__func__,__FILE__);
		BUG();
		goto cleanup;
	}

	/*
	 * If the indirect block is missing while we are reading
	 * the chain(ext3_get_branch() returns -EAGAIN err), or
	 * if the chain has been changed after we grab the semaphore,
	 * (either because another process truncated this branch, or
	 * another get_block allocated this branch) re-grab the chain to see if
	 * the request block has been allocated or not.
	 *
	 * Since we already block the truncate/other get_block
	 * at this point, we will have the current copy of the chain when we
	 * splice the branch into the tree.
	 */
	if (err == -EAGAIN || !verify_chain(chain, partial)) {
		while (partial > chain) {
			brelse(partial->bh);
			partial--;
		}
		partial = ext2_get_branch(inode, depth, offsets, chain, &err);
		if (!partial) {
			count++;
			if (err){
				printk("failed to allocate? %s %s\n",__func__,__FILE__);
				BUG();
				goto cleanup;
			}
			goto got_it;
		}
	}

	/*
	 * Okay, we need to do block allocation.  Lazily initialize the block
	 * allocation info here if necessary
	*/
	if (S_ISREG(ei->ext2_raw_inode.i_mode) && (!ei->i_block_alloc_info))
		ext2_init_block_alloc_info(inode);

	goal = ext2_find_goal(inode, iblock, partial);

	/* the number of blocks need to allocate for [d,t]indirect blocks */
	indirect_blks = (chain + depth) - partial - 1;

	/*
	 * Next look up the indirect map to count the totoal number of
	 * direct blocks to allocate for this branch.
	 */
	count = ext2_blks_to_allocate(partial, indirect_blks,
					maxblocks, blocks_to_boundary);

	/*
	 * XXX ???? Block out ext2_truncate while we alter the tree
	 */
	err = ext2_alloc_branch(inode, indirect_blks, &count, goal,
				offsets + (partial - chain), partial);


	if (err) {
		printk("failed to to mapping. %s %s\n",__func__,__FILE__);
		BUG();
		goto cleanup;
	}


	ext2_splice_branch(inode, iblock, partial, indirect_blks, count);
got_it:
	
	ret_block = le32_to_cpu(chain[depth-1].key);
	err = count;
	/* Clean up and exit */
	partial = chain + depth - 1;	/* the whole chain */
cleanup:
	while (partial > chain) {
		brelse(partial->bh);
		partial--;
	}
	return ret_block;
}

static unsigned long ext2_inode_bmap(struct inode *inode, loff_t off)
{
	unsigned long iblock;
	iblock = (off/* + EXT2_BLOCK_SIZE-1*/) >> EXT2_BLOCK_BITS;
	//iblock = (off + EXT2_BLOCK_SIZE-1) >> EXT2_BLOCK_BITS;
	unsigned long ret_iblock;

	ret_iblock = ext2_get_blocks(inode,iblock,1,1);

	return ret_iblock;
}

static int ext2_inode_blocksize(struct inode *inode)
{
	return EXT2_BLOCK_SIZE;
}

/*
 * Maximal file size.  There is a direct, and {,double-,triple-}indirect
 * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
 * We need to be 1 filesystem block less than the 2^32 sector limit.
 */
static loff_t ext2_max_size(int bits)
{
  loff_t res = EXT2_NDIR_BLOCKS;
  int meta_blocks;
  loff_t upper_limit;

  /* This is calculated to be the largest file size for a
   * dense, file such that the total number of
   * sectors in the file, including data and all indirect blocks,
   * does not exceed 2^32 -1
   * __u32 i_blocks representing the total number of
   * 512 bytes blocks of the file
   */
  upper_limit = (1LL << 32) - 1;
    
  /* total blocks in file system block size */
  upper_limit >>= (bits - 9);
  
  
  /* indirect blocks */
  meta_blocks = 1;
  /* double indirect blocks */
  meta_blocks += 1 + (1LL << (bits-2));
  /* tripple indirect blocks */
  meta_blocks += 1 + (1LL << (bits-2)) + (1LL << (2*(bits-2)));

  upper_limit -= meta_blocks;
  upper_limit <<= bits;

  res += 1LL << (bits-2);
  res += 1LL << (2*(bits-2));
  res += 1LL << (3*(bits-2));
  res <<= bits;
  if (res > upper_limit)
    res = upper_limit;

  if (res > MAX_LFS_FILESIZE)
    res = MAX_LFS_FILESIZE;

  return res;
} 

static loff_t ext2_inode_max_filesize(struct inode *inode)
{
	return ext2_max_size(EXT2_BLOCK_BITS);
}

static void ext2_inode_update(struct inode *inode, time_t atime, time_t mtime, time_t ctime)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info *)inode->i_data;

	if(atime)
		ei->ext2_raw_inode.i_atime = atime;
	if(mtime)
		ei->ext2_raw_inode.i_mtime = mtime;
	if(ctime)
		ei->ext2_raw_inode.i_ctime = ctime;
}

static nlink_t ext2_inode_change_nlinks(struct inode *inode, int change)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info *)inode->i_data;

	ei->ext2_raw_inode.i_links_count += change;

	//printk("i_links_count: %d\n",ei->ext2_raw_inode.i_links_count);

	return ei->ext2_raw_inode.i_links_count;
}

static int ext2_inode_get_name_of_son(
	struct inode * fino, ino_t inum, char * name, int size
	)
{
	//unsigned reclen = EXT2_DIR_REC_LEN(size);
	struct ext2_inode_info *ei = EXT2_I(fino);
	struct ext2_dirent *ent=NULL;
	struct buf_head *bh;
	loff_t pos = 0;
	ext2_fsblk_t block = 0;
	u8_t *kaddr;

	for(pos = 0; pos<ei->i_size; pos += EXT2_BLOCK_SIZE){
		block = ext2_inode_bmap(fino,pos);
		if(unlikely(block == NOBLK || block == 0)){
			printk("bmap error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		bh = sd_bread(fino->i_dev,block*EXT2_BLOCK_GRAN);
		if(!bh){
			printk("sd_bread error. %s %s\n",__func__,__FILE__);
			BUG();
		}
		
		kaddr = bh->b_data;
		ent = (struct ext2_dirent *)kaddr;
		kaddr += ext2_last_byte(ei,pos>>EXT2_BLOCK_BITS);// - reclen;
		while((u8_t*)ent < kaddr){
			if(ent->rec_len == 0){
				printk("Invalid dir entry. \n");
				BUG();
			}
			if(ent->inode==inum){
				/*
				 *we can not use size here, because it denotes the max space of name.
				 *Also be careful that strncpy appends a '\0' at the end.
				 */
				strncpy(name, ent->name, ent->name_len+1);
				//strncpy(name, ent->name, size);
				brelse(bh);
				goto found;
			}
			ent = ext2_next_entry(ent);
		}
		brelse(bh);
	}	
	printk("%s failed in %s\n",__func__,__FILE__);
	return -ENOENT;
found:
	return 0;
} 

static int ext2_inode_stat(struct inode *inode, struct stat *inode_stat)
{
	struct ext2_inode_info *ei = (struct ext2_inode_info *)inode->i_data;

	inode_stat->st_dev = inode->i_dev;
	inode_stat->st_ino = inode->i_num;
	inode_stat->st_mode = ei->ext2_raw_inode.i_mode;
	inode_stat->st_nlink = ei->ext2_raw_inode.i_links_count;
	inode_stat->st_uid = ei->ext2_raw_inode.i_uid;
	inode_stat->st_gid = ei->ext2_raw_inode.i_gid;

	if(S_ISCHR(ei->ext2_raw_inode.i_mode) ||
		 S_ISBLK(ei->ext2_raw_inode.i_mode))
		inode_stat->st_rdev = (dev_t) ei->I_data[0];

	/*
	 *FIXME
	 *This field should be 64-bit long.
	 */
	inode_stat->st_size = (unsigned long)ei->i_size;
	inode_stat->st_blksize = EXT2_BLOCK_SIZE;

	inode_stat->st_blocks = ei->ext2_raw_inode.i_blocks;
	inode_stat->st_atime = ei->ext2_raw_inode.i_atime;
	inode_stat->st_atime_nsec = 0;
	inode_stat->st_mtime = ei->ext2_raw_inode.i_mtime;
	inode_stat->st_mtime_nsec = 0;
	inode_stat->st_ctime = ei->ext2_raw_inode.i_ctime;
	inode_stat->st_ctime_nsec = 0;

	return 0;
}

static int ext2_inode_readdir(int fd, struct dirent *dirp)
{
	int ret;
	struct ext2_dirent *d;
	off_t f_pos;

	d = (struct ext2_dirent*)kmalloc(sizeof(struct ext2_dirent),PageWait);
	if(!d){
		printk("Not enough memory. %s %s\n",__func__,__FILE__);
		BUG();
	}

again:
	f_pos = fget(fd)->f_pos;
	ret = do_read(fd, (char *)d, sizeof(struct ext2_dirent));
	if(ret < 0){
		kfree(d);
		return ret;
	}

	if(!ret){
		kfree(d);
		return 0;
	}
	//printk("ino: %u name: %s pos %d\n",d->inode,d->name,(unsigned)f_pos);
	//printk("ino: %u curino: %u\n",d->inode,current->pwd->i_num);

	if(!d->inode){
		//printk("BUG %s %s\n",__func__,__FILE__);
		//BUG();
		goto again;
	}

	if(put_user4(&dirp->d_ino, (d->inode == 1) ? ROOT_INODE : d->inode) < 0)
			goto failed;

	f_pos += ext2_rec_len_from_disk(d->rec_len);
	fget(fd)->f_pos = f_pos;
	if(put_user4(&dirp->d_off, f_pos) < 0)
		goto failed;

	if(put_user2(&dirp->d_reclen,
		((nameoff + d->name_len + 1) + 3) & (~3)) < 0)
		goto failed;

	if(memcpy_to_user(dirp->d_name, d->name, d->name_len) < 0)
		goto failed;

	if(put_user1(&dirp->d_name[d->name_len], '\0') < 0)
		goto failed;

	kfree(d);	
	return 1;

failed:
	kfree(d);
	return -EFAULT;
}

static int ext2_inode_readlink(struct inode *inode,char *buf,size_t size)
{
	struct ext2_inode_info *ei = inode->i_data;
	char *link = (char*)ei->I_data;
	int fsize = (int)ei->i_size;

	if(unlikely(fsize > EXT2_LINK_LEN)) {
		printk("a long ext2 symbolic link detected. %s %s \n",
			__func__,__FILE__);
		BUG();
	}
	memcpy_to_user(buf,link,fsize);
	return fsize;
}
